/**
 * Copyright (c) 2020-2024, huli.com
 * All rights reserved.
 */
package com.xiaohujr.xuexue.leetcode.meituan;

/**
 * @author Xue Xue (xuexue1@huli.com)
 * @version 1.0
 * @since 2021/3/1
 */
public class SellStock {
    public int maxProfit(int[] prices) {
        int[] dp = new int[prices.length];
        int min = prices[0];
        int ans = 0;
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(min, prices[i - 1]);
            ans = Math.max(ans, prices[i] - min);
        }
        return ans;
    }

    public int maxProfit3(int[] prices) {
            int[][][] dp = new int[prices.length][3][2];
            int ans = 0;
            dp[0][0][0] = 0;
            dp[0][1][1] = -prices[0];
            for (int i = 1; i < prices.length; i++) {
                dp[i][0][0] = 0;
                dp[i][1][1] = -prices[i];
                for (int j = 1; j < 3; j++) {
                    if(j>=2*i){
                        continue;
                    }
                    dp[i][j][1] = Math.max(dp[i - 1][j-1][0] - prices[i-1], dp[i - 1][j][1]);
                    dp[i][j][0] = Math.max(dp[i - 1][j][1] + prices[i-1], dp[i - 1][j][0]);

                    int max = Math.max(dp[i][j][0], dp[i][j][1]);
                    ans = Math.max(ans,max);
                }
            }
            return ans;
    }

    public static void main(String[] args) {
//        new SellStock().maxProfit(new int[]{7, 1, 5, 3, 6, 4});
        int i = new SellStock().maxProfit3(new int[]{1,2,3,4,5});
        System.out.println(i);
    }
}
